﻿#define  _CRT_SECURE_NO_WARNINGS

// set 的使用部分
#include <iostream>
#include <set>


using namespace std;


/////////////////////////////   set 的使用部分  ------ 双向迭代器

//set 是一个容器 -------------------- 对应 Key 模型 
// set 不支持修改

// set 支持的功能是 : 增删查 
// set 的底层是红黑树 , 红黑树是一棵平衡搜索树
// set 的时间复杂度是 : O(log N) ---- 最多搜索高度层

// set 迭代器遍历出来是有序的 , 那么对于平衡搜索树来说就是走的 ---- 中序

/////// set 优点可以达到去重

/////////// 构造部分

#if 0
int main()
{
	//默认构造
	set<int> s;

	//迭代器区间构造 + 列表构造
	set<int> s1{ 1,2,3 }; // 走initializer_list
	set<int> s2(s1.begin(), s1.end());


	//拷贝构造
	set<int> s3;
	s3 = s2;

	for (auto& e : s3)
	{
		cout << e << endl;
	}


	//C++11 列表构造
	set<string> s4{ "苹果","葡萄","香蕉","梨" };
	// set 默认是升序  ping  pu     x     l  -----  按字典序比较 

	for (auto& e : s4)
	{
		cout << e << endl;
	}

	return 0;
}
#endif



/////////// 迭代器部分

#if 0
int main()
{
	
	set<int> s1{ 1,2,3,4,5,6,7,8,9,10}; 
	
	// 迭代器遍历
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		// set 是 Key模型, 不支持修改
		//*it = 2; // err

		cout << *it << " ";
		++it;
	}

	cout << endl;

	set<int> s2{ 1,2,3,4,5,6,7,8,9,10 };
	//反向迭代器
	auto it1 = s2.rbegin();
	while (it1 != s2.rend())
	{
		// set 是 Key模型, 不支持修改
		//*it = 2; // err

		cout << *it1 << " ";
		++it1;
	}
	return 0;
}
#endif

/////////// set 可以去重 + 排序
#if 0
int main()
{
	// set 去重
	set<int> s{ 1,2,2,3,4,4,4,5,6 };
	// set 底层是红黑树,也就是平衡搜索树 , 那么插入就有非冗余版本 , set 不支持冗余可以达到去重
	for (auto& e : s)
	{
		cout << e << " ";
	}

	cout << endl << endl;


	//增加第二个模版参数 ----- 仿函数的使用 ----- 达到降序的效果
	set<int, greater<int>> s1{ 1,2,2,3,4,4,4,5,6 };
	// set 底层是红黑树,也就是平衡搜索树 , 那么插入就有非冗余版本 , set 不支持冗余可以达到去重
	for (auto& e : s1)
	{
		cout << e << " ";
	}
	cout << endl << endl;
	return 0;
}
#endif



/////////// set 增删查



///// -----------  增  --- insert /////

//////////////////// pair ---- 是一个模版
// template <class T1, class T2> struct pair;
//              |         |
//           first      second       --------------------- 都是 public 



// pair<iterator, bool> insert(const value_type & val);
// 返回值为 pair --- first 是 iterator , second 是 bool 
//                 a.  插入成功 , iterator -- 指向的是新的元素 , bool -- 为真
//                 b.  插入失败 , iterator -- 指向已经在set中的并且与插入元素相等的元素 , bool -- 为假

// 故 :  set 中的 insert 具有 : 1. 插入功能  2. 查找功能


#if 0
int main()
{
	// 插入单个值 
	//set<int> s; // 升序
	//给仿函数 
	set<int,greater<int>> s; // 降序
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);

	for (auto& e : s)
	{
		cout << e << " ";
	}

	cout << endl << endl;

	//迭代器区间插入
	set<int, greater<int>> s1;
	//双向迭代器不支持 + - 
	//s1.insert(s.begin(), s.begin() + 3);
	s1.insert(s.begin(), s.end());

	for (auto& e : s1)
	{
		cout << e << " ";
	}

	cout << endl << endl;

	// initializer_list 
	set<int> s2;
	s2.insert({1,1,2,3,3,4,5,5,6,6,6,6,7});
	// 这里走的是隐式类型转换 --- 先构造在拷贝优化后直接构造

	for (auto& e : s2)
	{
		cout << e << " ";
	}
	
	cout << endl << endl;

	////////////// 插入情况分析
	// a. 插入成功 , iterator -- 指向的是新的元素 , bool -- 为真

	//以下情况是插入
	pair<set<int>::iterator, bool> _insert;
	_insert = s2.insert(8);
	cout << *_insert.first << endl; // iterator 是迭代器是指针要访问时解引用

	cout << _insert.second << endl;


	//以下情况是查找 , 因为元素已经在 set 中了
	pair<set<int>::iterator, bool> find;
	find = s2.insert(1);
	cout << *find.first << endl; // iterator 是迭代器是指针要访问时解引用

	cout << find.second << endl;

	// 插入已经存在的值插入失败
	s2.insert({ 1,2,3 });
	cout << "再次插入 ---  1,2,3" << " : ";
	for (auto& e : s2)
	{
		cout << e << " ";
	}
	return 0;
}
#endif
#if 0 
///// -----------  删  --- insert /////
// 底层是红黑树 -- 平衡搜索树
// 删除分为两种情况 -- 1. 直接删除  2. 替代法删除

int main()
{

	set<int> s = { 4,2,7,2,8,5,9 };

	for (auto e : s)
	{
		cout << e << " ";
	} 

	cout << endl;

	// 删除最小值 -- 升序, 所以第一个是最小值
	s.erase(s.begin());
	for (auto e : s)
	{
		cout << e << " ";
	}


	///////  size_type erase (const value_type& val);
	//		 返回的是删除元素的个数

	// 直接删除x
	int x;
	cin >> x;
	int num = s.erase(x); // 返回的是 x 的个数

	if (num == 0)
	{
		cout << x << "不存在！" << endl;
	} 
	else
	{
		cout << x << "存在！并成功删除" << endl;
	}

	for (auto e : s)
	{
		cout << e << " ";
	} 

	cout << endl;


	// 直接查找在利用迭代器删除x
	cin >> x;
	auto pos = s.find(x);

	if (pos != s.end())
	{
		// 迭代器会失效 --- pos 失效 , 不能使用
		s.erase(pos);
		cout << x << "存在！并成功删除" << endl;
	}

	else
	{
		cout << x << "不存在！" << endl;
	}

	for (auto e : s)
	{
		cout << e << " ";
	}

	cout << endl;
}
#endif
#if 0
///// -----------  查  /////

//查找是根据二叉搜索树的方式查找,效率高 -- O(log N) 

int main()
{
	set<int> s = { 4,2,7,2,8,5,9 };
	// 算法库的查找 O(N)
	int x;
	//cin >> x;
	auto pos1 = find(s.begin(), s.end(), x);
	// set⾃⾝实现的查找 O(logN)
	auto pos2 = s.find(x);

	/////// 利⽤count间接实现快速查找
	//cin >> x;
	if (s.count(x))
	{
		cout << x << "在！" << endl;
	}
	else
	{
		cout <<" 不存在！" << endl;

	}

	///////// lower_bound ---- 返回大于等于位置的迭代器
	std::set<int> myset;
	for (int i = 1; i < 10; i++)
		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90

	for (auto e : myset)
	{
		cout << e << " ";
	}

	cout << endl;
	// 实现查找到的[itlow,itup)包含[30, 60)区间
	// 返回 >= 30
	auto itlow = myset.lower_bound(30);
	// 返回 > 60
	auto itup = myset.upper_bound(60);

	// 删除这段区间的值
	myset.erase(itlow, itup);
	for (auto e : myset)
	{
		cout << e << " ";
	} 

	cout << endl;

	return 0;
}
#endif


//////////////////////////////////////  multiset 的使用


// 与 set 不同之处 : 
// 1. multiset主要的特点就是支持冗余
// 2. 相比set不同的是，x可能会存在多个，find查找中序的第⼀个
// 3. count 返回的是实际个数 , 而 set 的 count 返回的是 0 / 1
// 4. lower_bound 和 upper_bound 在 multiset 中会有更大价值
#if 0
int main()
{
	multiset<int> mus;
	//差异 1 : 支持冗余, 不会去重 
	mus.insert(1);
	mus.insert(2);
	mus.insert(1);
	mus.insert(1);

	for (auto e : mus)
	{
		cout << e << " ";
	}

	cout << endl;


	mus.insert({ 1,2,3,4,1,1,5,6,7,4,4,4});

	for (auto e : mus)
	{
		cout << e << " ";
	}

	//差异 2 : find查找中序的第⼀个
	int x;
	cin >> x;
	auto pos = mus.find(x);
	// 因为是中序遍历是有序的, 查找的是中序的第一个 , 所以和其相等的值都会打印
	while (pos != mus.end() && *pos == x)
	{
		cout << *pos << " ";
		++pos;
	}

	cout << endl;


	//差异 3 : count 返回的是实际个数
	mus.insert({ 1,2,3,4,1,1 });

	for (auto e : mus)
	{
		cout << e << " ";
	}
	cout << endl;


	cout << x << " : " << mus.count(x);

	return 0;
}
#endif 

#if 0
///////////////// 4. lower_bound 和 upper_bound
// STL 中的区间都是左闭右开 ---- [ , )

int main()
{
	// lower_bound返回的是 >= 位置的迭代器 --- 即 :  闭区间

	// upper_bound返回的是 >  位置的迭代器

	multiset<int> mus{10,20,30,30,30,40,50,60,70,80};

	for (auto e : mus)
	{
		cout << e << " ";
	}
	cout << endl;


	//删除 30 - 60 区间 , 重复的也删
	//区间是左闭又开
	auto left = mus.lower_bound(30); // 返回第一个匹配的元素
	auto right = mus.upper_bound(60);//会返回 > 60 位置的迭代器

	mus.erase(left,right);


	for (auto e : mus)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}
#endif


int main()
{
	// lower_bound返回的是 >= 位置的迭代器 --- 即 :  闭区间

	// upper_bound返回的是 >  位置的迭代器

	multiset<int> mus{ 10,20,30,30,30,40,50,60,70,80 };

	for (auto e : mus)
	{
		cout << e << " ";
	}
	cout << endl;

	//有的全删
	mus.erase(30);


	for (auto e : mus)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}